package com.data_structure_algorithm.algorithm;

/**
 * @author 何章怀晓 hezhanghuaixiao
 * @version V1.0
 * @desc
 */
public class Maze {

  public static void main(String[] args) {
    //创建2维数组模拟迷宫

    int[][] map = new int[8][7];

    //1表示墙，不可逾越  初始化迷宫
    for (int i = 0; i < map.length; i++) {

      for (int j = 0; j < map[i].length; j++) {

        //行
        if (i == 0 || i == map.length - 1) {
          map[i][j] = 1;
        }
        //列
        if (j == 0 || j == map[i].length - 1) {
          map[i][j] = 1;
        }

        //索引为3的行，列索引为2的部分也是1
        if (i == 3 && j <= 2) {
          map[i][j] = 1;
        }
      }
    }





    for (int[] item : map
    ) {
      for (int ele : item
      ) {
        System.out.print(ele + " ");
      }
      System.out.println();
    }

    setWay(map, 1, 1);

    System.out.println("--------------------");

    //输出新的地图，引用类型在栈帧中，指向的是同一个
    for (int[] item : map
    ) {
      for (int ele : item
      ) {
        System.out.print(ele + " ");
      }
      System.out.println();
    }

  }

  /**
   * @param map 地图
   * @param i 起点行
   * @param j 起点列
   * @return boolean 找到返回true[路能走返回true反之false，每次调用都是走一格]
   * @describe 约定：(1,1)为起点，（6,5）为终点 1为墙，2为路，3死路 定义走路策略：下右上左，即优先级
   * @author 何章怀晓 hezhanghuaixiao
   * @date 2022/3/24  9:31
   * @other
   */
  public static boolean setWay(int[][] map, int i, int j) {
    if (map[6][5] == 2) {
      return true;
    } else {
      //约定：(1,1)为起点，（6,5）为终点 1为墙，2为路，3死路 定义走路策略：下右上左，即优先级
      //根据不同情况来确定
      if (map[i][j] == 0) {
        //该路未走过
        //下右上左
        //假设该路可走,如果不可走在修改
        map[i][j] = 2;
        if (setWay(map, i++, j)) {//下
          return true;
        } else if (setWay(map, i, j++)) {//右
          return true;
        } else if (setWay(map, i--, j)) {//上
          return true;
        } else if (setWay(map, i, j--)) {//左
          return true;
        } else {
          //以上均走不了，置为死路
          map[i][j] = 3;
          return false;
        }

        //墙
      } else if (map[i][j] == 1) {
        return false;
        //走过了
      } else if (map[i][j] == 2) {
        return false;
        //死路
      } else if (map[i][j] == 3) {
        return false;
      }
    }
    return false;
  }

}
